Міністерство освіти і науки України Національний університет «Львівська політехніка» Інститут комп’ютерних наук та інформаційних технологій Кафедра автоматизованих систем управління
Лабораторна робота №7 З курсу: «Комп’ютерна графіка»                            Тема: Алгоритм Брезенхема для генерації кола. Мета: Освоїти алгоритм побудови кола засобами комп’ютерної графіки ТЕОРЕТИЧНІ ОСНОВИ Один з найбільш ефективних і простих для розуміння алгоритмів генерації кола належить Брезенхему. Для початку відмітимо, що необхідно згенерувати тільки одну восьму частину кола. Інші його частини можуть бути отримані послідовними відображеннями, як це показано на рис. 5.1. Якщо згенерований перший октант (від 0 до 45° проти годинникової стрілки), то другий октант можна отримати дзеркальним відображенням відносно прямої y=х, що дає в сукупності перший квадрант. Перший квадрант відбивається відносно прямої х=0 для отримання відповідної частини кола в другому квадранті. Верхнє півколо відбивається відносно прямої y=0 для завершення побудови. На рис.5.1 наведені двовимірні матриці відповідних перетворень.
Рис.5.1. Генерація повного кола з дуги в першому октанті. Для виведення алгоритму розглянемо першу чверть кола з центром у початку координат. Помітимо, що якщо робота алгоритму починається в точці х=0, у=R, то при генерації кола за годинниковою стрілкою в першому квадранті у є монотонно спадною функцією аргумента х (рис.5.2). Аналогічно, якщо вихідною точкою є у=0, х=R, то при генерації кола проти годинникової стрілки х буде монотонно спадною функцією аргументу у. У нашому випадку вибирається генерація за годинниковою стрілкою з початком у точці х=0, у=R. Передбачається, що центр кола і початкова точка знаходяться точно в точках растра. Для будь-якої заданої точки на колі при генерації за годинниковою стрілкою існує тільки три можливості вибрати наступний піксел, що щонайкраще наближає коло: горизонтально вправо, по діагоналі вниз і вправо, вертикально вниз. На рис.5.3 ці напрямки позначені відповідно mH, mD, mV. Алгоритм вибирає піксел, для якого мінімальний квадрат відстані між одним з цих положень і колом, тобто мінімум з mH=|(xi+1)2+(yi)2-R2| mD=|(xi+1)2+(yi-1)2-R2| mV=|(xi)2+(yi-1)2-R2|
Рис. 5.2. Коло у першому квадранті. 
Рис.5.3. Вибір пікселів у першому квадранті.  Обчислення можна спростити, якщо зауважити, що в околі точки (xi, yi) можливі тільки п'ять типів перетинів кола і сітки растра, наведених на рис.5.4.
 Рис. 5.4. Перетини кола і сітки растра. Різниця між квадратами відстаней від центра кола до діагонального піксела (xi+1, уi-1) і від центра до точки на колі R2 дорівнює Di=(xi+1)2+(yi-1)2-R2 Як і в алгоритмі Брезенхема для відрізка, для вибору відповідного піксела бажано використовувати тільки знак похибки, а не її величину. При Di<0 діагональна точка (xi+1, уi-1) знаходиться всередині реального кола, тобто це випадки 1 або 2 на рис. 5.4. Ясно, що в цій ситуації варто вибрати або піксел (xi+1, уi), тобто mH, або піксел (xi+1, уi-1), тобто mD. Для цього спочатку розглянемо випадок 1 і перевіримо різницю квадратів відстаней від кола до пікселів у горизонтальному і діагональному напрямках: d=|(xi+1)2+(yi)2-R2|-|(xi+1)2+(yi-1)2-R2| При d<0 відстань від кола до діагонального піксела більша, ніж до горизонтального. Навпаки, якщо d>0, відстань до горизонтального піксела більша. Таким чином, при d<=0 вибираємо mH (xi+1, уi) при d>0 вибираємо mD (xi+1, уi-1) При d=0, коли відстань від кола до обох пікселів однакова, вибираємо горизонтальний крок. . Підіб'ємо підсумок отриманих результатів: Di<0 d<=0 вибираємо піксел (xi+1, уi)-mH d>0 вибираємо піксел (xi+1, уi-1)-mD Di>0 d'<=0 вибираємо піксел (xi+1, уi-1)- mD d'>0 вибираємо піксел (xi, уi-1)-mV Di=0 вибираємо піксел (xi+1, уi-1)-mD Реалізація алгоритму Брезенхема на псевдокоді для кола наводиться нижче.
Текст программного коду: unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, Grids, S...